package training;

import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_14_Training {
    //乘积为正数的最长子数组长度
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0]>0?1:0;
        g[0] = nums[0]<0?1:0;
        int max = f[0];
        for (int i = 1; i < n; i++) {
            if(nums[i]==0){
                f[i] = 0;
                g[i] = 0;
            }else if(nums[i]>0){
                f[i] = f[i-1] + 1;
                g[i] = g[i-1]==0?0:g[i-1]+1;
            }else {
                g[i] = f[i-1] + 1;
                f[i] = g[i-1]==0?0:g[i-1]+1;
            }
            max = Math.max(max,f[i]);
        }
        return max;
    }

    //连接所有点的最小费用
    static class edge{
        public int v;
        public int u;
        public int weight;

        public edge(int v, int u, int weight) {
            this.v = v;
            this.u = u;
            this.weight = weight;
        }
    }

    public List<edge> Edge = new ArrayList<>();
    public int[] perant;
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[][] v = new int[n+1][n+1];
        perant = new int[n+1];
        for (int i = 1; i <= n; i++) {
            perant[i] = i;
        }
        for (int i = 1; i <= n-1; i++) {
            for (int j = i+1; j <= n; j++) {
                int val = Math.abs(points[i-1][0]-points[j-1][0]) + Math.abs(points[i-1][1]-points[j-1][1]);
                v[i][j] = val;
                Edge.add(new edge(i,j,val));
            }
        }
        Edge.sort((a,b)->{
            return a.weight - b.weight;
        });

        int ret = kruskal(n);
        return ret;
    }

    public int find(int x){
        if(perant[x] != x){
            perant[x] = find(perant[x]);
        }
        return perant[x];
    }

    public void union(int x,int y){
        int rootx = find(x);
        int rooty = find(y);
        perant[rootx] = rooty;
    }

    public int kruskal (int n){
        int ret = 0;
        int count = 0;
        for(edge x : Edge){
            if(count == n-1) break;
            if(find(x.u) == find(x.v)){
                continue;
            }
            count++;
            ret += x.weight;
            union(x.u,x.v);
        }
        return ret;
    }

    //最长连续序列
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int max = -1;
        for (int i = 0; i < n; i++) {
            if(map.containsKey(nums[i]-1) && map.containsKey(nums[i]+1)){
                int left = nums[i]-1;
                int right = nums[i]+1;
                while(map.containsKey(left)){
                    map.replace(left,map.get(left)+1);
                    left--;
                }
                while(map.containsKey(right)){
                    map.replace(right,map.get(right)+1);
                    right--;
                }
                max = Math.max(max,map.get(left++));
            }else if(map.containsKey(nums[i]-1)){
                int left = nums[i]-1;
                while(map.containsKey(left)){
                    map.replace(left,map.get(left)+1);
                    left--;
                }
                max = Math.max(max,map.get(left++));
            }else if(map.containsKey(nums[i]+1)){
                int right = nums[i]+1;
                while(map.containsKey(right)){
                    map.replace(right,map.get(right)+1);
                    right--;
                }
                max = Math.max(max,map.get(right--));
            }else {
                map.put(nums[i],1);
                max = Math.max(max,1);
            }
        }
        return max;
    }

    //等差数列分化
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = dp[1] = 0;
        int sum = 0;
        for (int i = 2; i < n; i++) {
            dp[i] = nums[i] - nums[i-1] == nums[i-1] - nums[i-2]?dp[i-1]+1:0;
            sum += dp[i];
        }
        return sum;
    }

    //最长湍流子数组
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if(n==1) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = arr[0]==arr[1]?1:2;
        int max = dp[1];
        for (int i = 2; i < n; i++) {
            if((arr[i] - arr[i-1] > 0 && arr[i-1] - arr[i-2] < 0) || (arr[i] - arr[i-1] < 0 && arr[i-1] - arr[i-2] > 0)){
                dp[i] = dp[i-1]+1;
            }else if(arr[i] - arr[i-1] == 0){
                dp[i] = 1;
            }else {
                dp[i] = 2;
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        s = " "+s;
        int n = s.length();
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j >=0 ; j--) {
                String string = s.substring(j+1,i+1);
                if(dp[j] && set.contains(string)) {
                    dp[i] = true;
                    break;
                }
                else dp[i] = false;
            }
        }
        return dp[n-1];
    }

    //最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int n  = nums.length;
        int[] dp = new int[n];
        Arrays.fill(nums,1);
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j <=0 ; j--) {
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}





